package com.ffly.astar;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class AStar {
	LinkedList<NodePath> openList = new LinkedList<NodePath>();
	Set<String> openListContainSet = new TreeSet<String>();
	Set<String> closeList = new TreeSet<String>();

	NodePath start = null;
	NodePath target = null;
	boolean isRun = false;
	int [] maps;
	
	final int FLAG_WALL = 1;
	
	public AStar() {
		maps = new int[Params.COL * Params.ROW];

		for (int x = 0; x < Params.COL; x++) {
			maps[point2Idx(x, 0)] = FLAG_WALL;
			maps[point2Idx(x, Params.ROW - 1)] = FLAG_WALL;
		}

		for (int y = 0; y < Params.ROW; y++) {
			maps[point2Idx(0, y)] = FLAG_WALL;
			maps[point2Idx(Params.COL - 1, y)] = FLAG_WALL;
		}
	}
	
	public int point2Idx(int x,int y){
		return x + y * Params.COL;
	}
	
	public void setWall(int x,int y){
		if(!checkOutOfMap(x, y)){
			maps[point2Idx(x, y)] = FLAG_WALL;
		}
	}
	
	public boolean isWall(int x,int y){
		if(!checkOutOfMap(x, y)){
			return maps[point2Idx(x, y)] == FLAG_WALL;
		}
		return true;
	}

	/**
	 * 设置起点
	 * @param x
	 * @param y
	 */
	public void setStartPoint(int x, int y) {
		start = new NodePath();
		start.x = x;
		start.y = y;
	}

	/**
	 * 设置终点
	 * @param x
	 * @param y
	 */
	public void setEndPoint(int x, int y) {
		target = new NodePath();
		target.x = x;
		target.y = y;
	}
	
	
	/**
	 * 重置参数
	 */
	public void reset(){
		openList.clear();
		closeList.clear();
		openListContainSet.clear();
		for(int i=0;i<maps.length;i++){
			maps[i] = 0;
		}
		isRun = false;
	}

	/**
	 * 计算路径
	 * @return
	 */
	public List<TwoValue<Integer, Integer>> runLogic() {
		NodePath tmp = start;
		isRun = true;
		openList.clear();
		closeList.clear();
		openListContainSet.clear();
		while (isRun) {
			// 逻辑流程
			// 1.把走过的点，都加入到closeList
			// 2.把可以走的点，都加入到openList
			// 3.每次取openList里面得分最小的值作为下一步要走的路
			closeList.add(tmp.getXYString());
			calc(tmp, target.x, target.y);
			Collections.sort(openList);

			if(openList.isEmpty()){
				System.out.println("----open List is Empty----");
				break;
			}

//			do{
				tmp = openList.removeLast();//下一步
//			}while(closeList.contains(tmp.getXYString()) && !openList.isEmpty());
			
			if (tmp.x == target.x && tmp.y == target.y) {
				System.out.println("----search path done.----");
				break;
			}
		}
		
		//组装结果
		List<TwoValue<Integer, Integer>> result = new ArrayList<TwoValue<Integer,Integer>>();
		do{
			//通过最后的终点节点，一直找父节点
			result.add(new TwoValue<Integer, Integer>(tmp.x, tmp.y));
			tmp = tmp.parent;
		}while(tmp!=null);
		
		return result;
	}

	/**
	 * 计算可以走的点
	 * @param root
	 * @param targetX
	 * @param targetY
	 */
	private void calc(NodePath root, int targetX, int targetY) {
		for (int i = 0; i < 8; i++) {//能走的8个方位
			NodePath path = NodePath.create(root, i, targetX, targetY);
			if (!checkOutOfMap(path.x, path.y)//超出地图 不能走
					&& !closeList.contains(path.getXYString()) //在closeList的点不能走
					&& !isWall(path.x , path.y) //墙上禁止行走
					&& !openListContainSet.contains(path.getXYString())
					) {
				openList.add(path);
				openListContainSet.add(path.getXYString());
			}
		}
	}

	/**
	 * 检测超出范围
	 * @param x
	 * @param y
	 * @return
	 */
	private static boolean checkOutOfMap(int x, int y) {
		if (x >= 0 && x < Params.COL && y >= 0 && y < Params.ROW) {
			return false;
		}
		return true;
	}
}
